package LeetCode;

public class DistinctSubsequences
{
  /*Solution: using dynamic programming. Initiating a two dimensional array of m*n, where n and m are the lengths of S and T respectively. 
   * An array entry array[i][j] indicate the number of subsequences of the first i characters in T, within the first j characters in S. 

First, initiating the first line. The if S.charAt(0) and T.charAt(0) is the same, the first entry of array should be 
1. Then we look if the first character of T appear again in S. If so, we increment the value of the entry by one.
2. The first column except array[0][0] should all be 0.
3. Then, updating the inside elements.
     if the ith character of T is the same as the jth character of S, a new match occurs. 
     array[i][j] is calculated by summing up the entry in its left up cell (indicating the condition before handling the current characters in both array) 
     and the entry in its left cell (indicating the matching before introducing the current character in array S).
If they are not the same, just copy the number from its left cell, indicating there is no new match.
4. In the end, simply return array[n-1][m-1].

     r  a  b  b  b  i  t
r   1  1  1  1  1  1  1
a   0  1  1  1  1  1  1 
b   0  0  1  2  3  3  3
b   0  0  0  1  3  3  3
i   0  0  0  0  0  3  3
t   0  0  0  0  0  0  3*/

  // DP f(i,j) = f(i-1,j) + s[i]==t[i] ? f(i-1,j-1) : 0
  // pass both
  public int numDistinct(String S, String T)
  {
    int[] occurence = new int[T.length() + 1];
    occurence[0] = 1;
    for (int i = 0 ; i < S.length() ; i++) {
      for (int j = T.length() - 1 ; j >= 0 ; j--)
        if (S.charAt(i) == T.charAt(j)) {
          if (occurence[j] > 0) occurence[j + 1] += occurence[j];
        }
    }
    return occurence[T.length()];

  }
  
  public int numDistinct1(String S, String T)
  {
    int m = S.length();
    int n = T.length();

    if (m == 0 || n == 0) return 0;
    // use dp, set up a two dimensional array to keep the temporal result
    int[][] array = new int[n][m];
    // initiate the result of comparing first characters
    if (S.charAt(0) == T.charAt(0)) {
      array[0][0] = 1;
    }
    // initiate the first line
    for (int j = 1 ; j < m ; j++) {
      if (S.charAt(j) == T.charAt(0)) {
        array[0][j] = array[0][j - 1] + 1;
      }
      else {
        array[0][j] = array[0][j - 1];
      }
    }
    // keep going through each character
    // if two characters are same, result is the current number
    // + previous number of matched sequence before this character
    // otherwise, keep the current number
    for (int i = 1 ; i < n ; i++) {
      for (int j = 1 ; j < m ; j++) {
        if (T.charAt(i) == S.charAt(j)) {
          array[i][j] = array[i - 1][j - 1] + array[i][j - 1];
        }
        else {
          array[i][j] = array[i][j - 1];
        }
      }
    }

    return array[n - 1][m - 1];
  }

  /**
   * @param args
   */
  public static void main(String[] args)
  {
    // TODO Auto-generated method stub
    DistinctSubsequences d = new DistinctSubsequences();
    System.out.println(d.numDistinct("rrabbbit", "abbbit"));
  }

}
